package Search_07;

/*
 * @Author 罗
 * @date 2020/3/19 - 11:11 上午
 * 插值查找算法
 */

import org.junit.Test;

public class InsertValueSearch_03 {
    @Test
    public void test() {
        int[] array = new int[100];
        for (int i = 0; i < array.length; i++) {
            array[i] = i;
        }
        int findValue = 889;
        int index = insertValueSearch(array, 0, array.length - 1, findValue);
        System.out.println(findValue + "的下标是" + index);
    }

    static int count = 0;

    /**
     * 插值查找算法
     *      注意事项：
     *
     * 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
     * 关键字分布不均匀的情况下，该方法不一定比折半查找要好
     * @param array
     * @param left
     * @param right
     * @param findValue
     * @return
     */
    public static int insertValueSearch(int[] array, int left, int right, int findValue) {
        System.out.println("第" + (count++) + "次调用");
        /*
        * 插值查找算法，必须判断findValue，否则会数组索引越界
        * */
        if (left > right || findValue < array[0] || findValue > array[array.length - 1]) {
            return -1;
        }
        int mid = left + (right - left) * (findValue - array[left]) / (array[right] - array[left]);

        if (findValue == array[mid]) {
            return mid;
        } else if (findValue > array[mid]) {
            return insertValueSearch(array, mid + 1, right, findValue);
        } else if (findValue < array[mid]) {
            return insertValueSearch(array, left, mid - 1, findValue);
        }
        return -1;
    }
}
